package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2020-11-26 11:16
 *
 * https://leetcode-cn.com/problems/partition-list/
 */
public class _86_分隔链表 {

    public ListNode partition(ListNode head, int x) {

        if (head == null) {

            return null;
        }

        ListNode ltHeadNode = new ListNode(0), ltTailNode = ltHeadNode;
        ListNode lgHeadNode = new ListNode(0), lgTailNode = lgHeadNode;

        while (head != null) {

            if (head.val < x) {

                ltTailNode.next = head;
                ltTailNode = head;
            }else {

                lgTailNode.next = head;
                lgTailNode = head;
            }

            head = head.next;
        }

        ltTailNode.next = lgHeadNode.next;
        lgTailNode.next = null;

        return ltHeadNode.next;
    }
}
